package com.zhang.二叉树;

import java.util.Comparator;

/**
 * @author 张吉鑫
 * @Description 平衡二叉搜索树
 * @date 2021/3/17 21:30
 */
public class BBST<E> extends BST<E>{
    public BBST() {
    }

    public BBST(Comparator comparator) {
        super(comparator);
    }

    /**
     * 左旋转
     * @param grand
     */
    protected void rotateLeft(Node<E> grand){
        Node<E> parent = grand.right;
        Node<E> child = parent.left;
        grand.right = child;
        parent.left = grand;

        afterRotate(grand, parent, child);
    }

    /**
     * 右旋转
     * @param grand
     */
    protected void rotateRight(Node<E> grand){
        Node<E> parent = grand.left;
        Node<E> child = parent.right;
        grand.left = child;
        parent.right = grand;

        afterRotate(grand, parent, child);
    }

    /**
     * 旋转后 调整父节点
     * @param grand
     * @param parent
     * @param child
     */
    protected void afterRotate(Node<E> grand,Node<E> parent,Node<E> child){
        if (grand.parent == null){
            root = parent;
        }else if (grand.isLeftChild()){
            grand.parent.left = parent;
        }else {
            grand.parent.right = parent;
        }
        parent.parent = grand.parent;
        grand.parent = parent;

        if (child != null){
            child.parent = grand;
        }

    }

    /**
     * 统一旋转
     * @param parent
     * @param a
     * @param b
     * @param c
     * @param d
     * @param e
     * @param f
     * @param g
     */
    protected void uniformRotation(Node<E> parent,//根节点
                                 Node<E> a, Node<E> b,Node<E> c ,
                                 Node<E> d,
                                 Node<E> e,Node<E> f,Node<E> g){
        b.left = a;
        b.right = c;

        f.left = e;
        f.right = g;

        d.left = b;
        d.right = f;

        d.parent = parent.parent;
        if (parent.parent == null){
            root = d;
        }else if (parent.isLeftChild()){
            parent.parent.left = d;
        }else if (parent.isRightChild()){
            parent.parent.right = d;
        }

        if (a != null){
            a.parent = b;
        }
        if (c != null){
            c.parent = b;
        }
        if (e != null){
            e.parent = f;
        }
        if (g != null){
            g.parent = f;
        }
        b.parent = d;
        f.parent = d;

    }

}
